package 打家劫舍动态规则;

import org.junit.Assert;

/**
 * 打家劫舍  动态规则
 * 你是一个专业的小偷，计划偷窥沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窥的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一个晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下，一夜之内能够偷窥到的最高金额。
 * <p>
 * 输入：[1,2,3,1]  输出：4
 * 输入：[2,7,9,3,1]  输出：12
 */
public class Solution {
    public static void main(String[] args) {

        int[] nums1 = {1, 2, 3, 1};
        int[] nums2 = {2, 7, 9, 3, 1};

        int res = maxMoney(nums1, 3);
        System.out.println("res = " + res);

        res = maxMoney(nums2, 4);
        System.out.println("res = " + res);


        res = dps(nums1);
        System.out.println("res = " + res);

        res = dps(nums2);
        System.out.println("res = " + res);


        res = dps2(nums1);
        System.out.println("res = " + res);

        res = dps2(nums2);
        System.out.println("res = " + res);


        res = Math.max(dps3(nums1, 0, nums1.length - 2), dps3(nums1, 1, nums1.length - 1));
        System.out.println("res = " + res);

        res = Math.max(dps3(nums2, 0, nums1.length - 2), dps3(nums2, 1, nums1.length - 1));
        System.out.println("res = " + res);


        TreeNode node5 = new TreeNode(1, null, null);
        TreeNode node4 = new TreeNode(3, null, null);
        TreeNode node3 = new TreeNode(3, null, node5);
        TreeNode node2 = new TreeNode(2, null, node4);
        TreeNode node1 = new TreeNode(3, node2, node3);
        int[] maxMoney = dfs(node1);
        res = Math.max(maxMoney[0], maxMoney[1]);
        System.out.println("res = " + res);
        Assert.assertEquals(7, res);

    }

    private static int maxMoney(int[] nums, int index) {

        if (null == nums || index < 0) {
            return 0;
        }
        if (index == 0) {
            return nums[index];
        }

        return Math.max(
                // 相邻最优解
                maxMoney(nums, index - 1),
                // 隔一个的最优解
                maxMoney(nums, index - 2) + nums[index]);
    }

    /**
     * 动态规划
     * 重点：
     * 1、最优子结构   n -> n-1 -> n-2
     * 2、递推公式     max(n-1, (n-2)+n)
     * 3、重叠子问题
     */
    private static int dps(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int[] cache = new int[nums.length];

        cache[0] = nums[0];
        cache[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            cache[i] = Math.max(cache[i - 1], cache[i - 2] + nums[i]);
        }

        return cache[cache.length - 1];
    }

    /**
     * 优化空间复杂度
     */
    private static int dps2(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int first = nums[0];
        int second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            int tmp = second;
            second = Math.max(first + nums[i], second);
            first = tmp;
        }

        return second;
    }

    /**
     * 房间首尾相连
     * 判断 去头 还是 去尾 是最优解
     */
    private static int dps3(int[] nums, int start, int end) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int first = nums[start];
        int second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int tmp = second;
            second = Math.max(first + nums[i], second);
            first = tmp;
        }

        return second;
    }

    /**
     * 二叉树 + 动态规划
     */
    private static int[] dfs(TreeNode node) {
        // {选择当前节点的最优解, 不选择当前节点的最优解}
        if (node == null) {
            return new int[]{0, 0};
        }

        int[] l = dfs(node.left);
        int[] r = dfs(node.right);

        // 选择当前节点的最优解, 求左右子节点选情况下的最优解
        int currentSelect = node.v + l[1] + r[1];
        // 不选择当前节点的最优解，求左右子节点最优解的和
        int currentNoSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{currentSelect, currentNoSelect};
    }

    static class TreeNode {
        int v;
        TreeNode left;
        TreeNode right;

        public TreeNode(int v, TreeNode left, TreeNode right) {
            this.v = v;
            this.left = left;
            this.right = right;
        }
    }

}
